home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 185_01 / bose.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-08-19  |  1.4 KB  |  143 lines
  1. /* Recursive version of Bose-Nelson sort */
  2. /* by Mark D. Lougheed */
  3. /* 2-SEP-85 */
  4.  
  5. #include "stdio.h"
  6.  
  7. /* #define DEBUG */
  8.  
  9.  
  10. int count=0;
  11. FILE *fp;
  12.  
  13.  
  14.  
  15. main(argc, argv)
  16. int argc;
  17. char **argv;
  18. {
  19. int n;
  20.  
  21.  
  22. if(argc < 3)
  23.     {
  24.     printf("USAGE: BOSE n outfile\n");
  25.  
  26.     exit();
  27.     }
  28.  
  29. else
  30.     {
  31.     n=atoi(*(++argv));
  32.  
  33.     if( ( fp=fopen(*(++argv), "w") )==0 )
  34.         {
  35.         printf("Error: could not open %s for writing.\n", *argv);
  36.  
  37.         exit();
  38.         }
  39.  
  40.     p2(1,n);
  41.  
  42.     printf("There were %d swaps\n",count);
  43.  
  44.     fclose(fp);
  45.     }
  46. }
  47.  
  48.  
  49. p1(x, y)
  50. int x, y;
  51. {
  52. fprintf(fp, "swap(%d,%d);\n", x, y);
  53.  
  54. ++count;
  55. }
  56.  
  57.  
  58. p2(i, x)
  59. int i, x;
  60. {
  61. int a;
  62.  
  63.  
  64. if(x!=1)
  65.     {
  66. #ifdef DEBUG
  67.     printf("p2:  i=%d, x=%d\n", i, x);
  68. #endif
  69.  
  70.     a=x/2;
  71.  
  72.     p2(i, a);
  73.  
  74.     p2(i+a, x-a);
  75.  
  76.     p3(i, a, i+a, x-a);
  77.     }
  78. }
  79.  
  80.  
  81. p3(i, x, j, y)
  82. int i, x, j, y;
  83. {
  84. int a, b;
  85.  
  86.  
  87. #ifdef DEBUG
  88. printf("p3:  i=%d, x=%d, j=%d, y=%d\n", i, x, j, y);
  89. #endif
  90.  
  91. a=x/2;
  92.  
  93. if(even(x))
  94.     {
  95. #ifdef DEBUG
  96.     puts("p3: x is even");
  97. #endif
  98.     
  99.     b=(y+1)/2;
  100.     }
  101.  
  102. else
  103.     {
  104. #ifdef DEBUG
  105.     puts("p3: x is odd");
  106. #endif
  107.     b=y/2;
  108.     }
  109.  
  110. if( (x==1) && (y==1) )
  111.     p1(i, j);
  112.  
  113. else if( (x==1) && (y==2) )
  114.     {
  115.     p1(i, j+1);
  116.  
  117.     p1(i, j);
  118.     }
  119.  
  120. else if( (x==2) && (y==1) )
  121.     {
  122.     p1(i, j);
  123.  
  124.     p1(i+1, j);
  125.     }
  126.  
  127. else
  128.     {
  129.     p3(i, a, j, b);
  130.  
  131.     p3(i+a, x-a, j+b, y-b);
  132.  
  133.     p3(i+a, x-a, j, b);
  134.     }
  135. }
  136.  
  137.  
  138. even(x)
  139. int x;
  140. {
  141. return(1-(1&x));
  142. }
  143.